package structures;

import structures.LinkedList.LinkedNode;

public class LinkedLists {

    /**
     * 判断单向链表是否有环，并返回环的入口节点
     *
     * @param header
     * @param <T>
     * @return
     */
    public static <T> LinkedNode<T> circleEntry(LinkedNode<T> header) {

        if (header == null) return null;

        LinkedNode<T> slow = header, fast = header;

        while ((slow = slow.next) != null &&
            fast.next != null &&
            (fast = fast.next.next) != null) {
            if (slow == fast) {
                slow = header;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    public static <T> LinkedNode<T> firstIntersection(LinkedNode<T> header1, LinkedNode<T> header2) {

        LinkedNode<T> entrance1 = circleEntry(header1);
        LinkedNode<T> entrance2 = circleEntry(header2);
        if (entrance1 == null)
            return entrance2 != null ? null : firstIntersection(header1, header2, null);

        if (entrance2 == null) return null;

        if (entrance1 == entrance2) {
            return firstIntersection(header1, header2, entrance1);
        }
        LinkedNode<T> p1 = header1;
        LinkedNode<T> p2 = header2;
        for (; ; ) {
            if (p1 == entrance1) return entrance1;
            if (p2 == entrance2) return entrance2;
            //是环，不用判空
            p1 = p1.next;
            p2 = p2.next;
        }
    }

    /**
     * @param header1 header o first linked list
     * @param header2 header of second linked list
     * @param bounds  the bounds(inclusive) to terminate.
     *                If it is null, it represents the tail of the linked list
     * @param <T>
     * @return
     */
    private static <T> LinkedNode<T> firstIntersection(LinkedNode<T> header1, LinkedNode<T> header2, LinkedNode<T> bounds) {
        if (header1 == null || header2 == null) {
            return null;
        }
        int shortLen;
        int len = 0;
        LinkedNode<T> terminate = bounds;
        if (bounds != null) {
            if (bounds.next != bounds) {
                terminate = bounds.next;
            } else terminate = null;
        }

        LinkedNode<T> p1 = header1, p2 = header2;
        LinkedNode<T> longL, shortL;
        for (; ; ) {
            if (p1 != null && p1 != terminate) {
                if (p1 == p2) return p1;
                len++;
                p1 = p1.next;
                if (p2 != null && p2 != terminate) {
                    p2 = p2.next;
                } else {
                    shortLen = len - 1;
                    while ((p1 = p1.next) != null && p1 != terminate) {
                        len++;
                    }
                    longL = header1;
                    shortL = header2;
                    break;
                }

            } else {
                if (p2 == null || p2 == terminate) {
                    return null;
                }
                len++;
                shortLen = len - 1;
                while ((p2 = p2.next) != null && p2 != terminate) {
                    len++;
                }
                longL = header2;
                shortL = header1;
                break;
            }
        }
        int det = len - shortLen;

        LinkedNode<T> pl = longL;

        while (pl != null) {
            if (det == 0) {
                LinkedNode<T> ps = shortL;
                for (int i = 0; i < shortLen; i++) {
                    if (ps == pl) return ps;
                    else {
                        pl = pl.next;
                        ps = ps.next;
                    }
                }
            } else {
                pl = pl.next;
                det--;
            }
        }
        return null;

    }

    public static void main(String[] args) {
        LinkedNode<Integer> header1 = new LinkedNode<>(0, "header1");
        LinkedNode<Integer> n1 = new LinkedNode<>(1, "n1");
        LinkedNode<Integer> n2 = new LinkedNode<>(2, "n2");
        LinkedNode<Integer> n3 = new LinkedNode<>(3, "n3");
        LinkedNode<Integer> n4 = new LinkedNode<>(4, "n4");
        LinkedNode<Integer> n5 = new LinkedNode<>(5, "n5");
        LinkedNode<Integer> n6 = new LinkedNode<>(6, "n6");
        LinkedNode<Integer> n7 = new LinkedNode<>(7, "n7");

        LinkedNode<Integer> header2 = new LinkedNode<>(0, "header2");
        LinkedNode<Integer> m1 = new LinkedNode<>(2, "m1");
        LinkedNode<Integer> m2 = new LinkedNode<>(2, "m2");
        LinkedNode<Integer> m3 = new LinkedNode<>(3, "m3");
        LinkedNode<Integer> m4 = new LinkedNode<>(2, "m4");
        header1.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n4;


        header2.next = m1;
        m1.next = m2;
        m2.next = n6;
        m3.next = n6;
        m4.next = n6;

        System.out.println(firstIntersection(header1, header2));
    }
}
